//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 569 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] result=new int[k];
        for (int i = 0; i < k; i++) {
            result[i]=arr[i];
        }
        return result;
    }


}

class minHeap{
    private int size=0;
    private int[] nums;

    public void offer(int offered){
        if(size==nums.length){
            return;
        }
        up(offered);
        size++;
    }

    public void up(int offered){
        int child=size;
        while (child>0){
            int parent=(child-1)/2;
            if(offered<nums[parent]){
                nums[child]=nums[parent];
            }else {
                break;
            }
            child=parent;
        }
        nums[child]=offered;
    }

    public int peek(){
        return nums[0];
    }

    public void down(int parent){
        while (true) {
            int left = parent * 2 + 1;
            int right = left + 1;
            int min=parent;
            if(left<size&&nums[min]>nums[left]){
                min=left;
            }
            if(right<size&&nums[min]>nums[right]){
                min=right;
            }
            if(min==parent){
                break;
            }
            swap(nums,min,parent);
            parent=min;
        }
    }

    public void swap(int[] nums,int i,int j){
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[j]^nums[i];
        nums[i]=nums[i]^nums[j];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
